package ljl.alg.wangzheng_camp.round1.dp;

public class _offer14_1_cut_rope {
    
    /**
     * 路人这个 dp 真心不错
     * */
    static class dp {
        public int cuttingRope(int n) {
            int[] dp = new int[n + 1];
            dp[2] = 1;
            for (int i = 3; i <= n; i++) {
                for (int j = 2; j < i; j++) {
                    dp[i] = Math.max(dp[i], j * Math.max(i - j, dp[i - j]));
                }
            }
            return dp[n];
        }
    }
    
    static class greedy {
        public int cuttingRope(int n) {
            if (n < 4) return n - 1;
            int res = 1;
            while (n > 4) {
                res *= 3;
                n -= 3;
            }
            return res * n;
        }
    }
    
    /**
     * 路飞的写起来没上面那个简单，但是怎么来的？为什么分解成 2 和 3 的乘积？
     *
     * 均值不等式，值越接近乘积越大，设分成 x 段，每段长度就是 n/x，乘积就是 n^x * (1/x)^x。。
     * 设错了，应该设每段长度是 x，则乘积为 x^(n/x) 也就是 (x^(1/x))^n
     * 转为求 x^(1/x) 了，求导
     *
     * 不好求，设 y = x ^ (1/x)，先两遍取对数 lny = 1/x * lnx，再求导
     * 1/y * y' = -1 / x2 * lnx + 1/x2 = (1 - lnx) / x2
     *
     * 所以 y' = (1 - lnx) / x2 * x ^ (1/x)
     * (0, e) (e, inf) 分别是正、负，所以 y 在 e 这是极大值
     *
     * y 可以取 2 或 3
     * 试了试，3 更大一点，所以应该选 3
     * */
    static class lufei {
        public int cuttingRope(int n) {
            if (n <= 3) return n - 1;
            final int p = (int) 1e9 + 7;
            int count3 = n / 3, r = n % 3;
            if (r == 0) return (int) ((long) Math.pow(3, count3) % p);
            if (r == 1) return (int) ((long) Math.pow(3, count3 - 1) * 4 % p);
            return (int) ((long) Math.pow(3, count3) * 2 % p);
        }
    }
}
